//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
using namespace std;

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size();
        int n = s2.size();
        int t = s3.size();
        if(m+n!=t)return false;
        //dp[i][j]：
        //s1的前i个字符和s2的前j个字符是否可以交错组成s3的前i+j个字符
        vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
        //状态初始化
        dp[0][0] = true;
        //第一列
        for (int i = 1; i <=m ; ++i) {
            if (s1[i-1]==s3[i-1]){
                dp[i][0] = true;
            }else{
                break;
            }
        }
        //第一行
        for (int i = 1; i <=n ; i++) {
            if(s2[i-1]==s3[i-1]){
                dp[0][i] = true;
            }else{
                break;
            }
        }

        //状态转移
        for (int i = 1; i <=m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int k = i+j;
                //判断i-1 与k-1 若相等看dp[i-1][j]
                if(s1[i-1]==s3[k-1] && dp[i-1][j]){
                    dp[i][j] = true;
                    //判断j-1 与k-1若相等看dp[i][j-1]
                }else if(s2[j-1]==s3[k-1] && dp[i][j-1]){
                    dp[i][j] = true;
                }else{
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
};